package com.yulongtian.oneProblemEveryDay.month202303;

/**
 * https://leetcode.cn/problems/minimum-deletions-to-make-string-balanced/
 *参考
 * @author yulongTian
 * @create 2023-03-06 20:58
 */
public class Test05 {
    public static void main(String[] args) {

    }

    public int minimumDeletions(String s) {
        int countB = 0, dp = 0;  // 令dp表示将s[0,i]变平衡最少需要删除的次数
        for (char c : s.toCharArray()) {
            if (c == 'a') {
                dp = Math.min(dp + 1, countB);  // 末尾出现a的时候，2个选择：1、删除这个a，然后将s[0,i-1]变平衡；2、保留这个a，删除前面所有的b
            } else {
                ++countB;  // 出现b的时候，最后面的b不需要删除，dp不变，b的个数加1就好
            }
        }
        return dp;
    }

}
